Certain approaches for implementing basic arithmetic in quantum devices, such as additions—and building on this then the entire stack of modular additions, multiplications, and exponentiations used to implement Shor's algorithm—assume that ancillas (ancilla qubits) are available that are in a known state. In quantum computing, ancillas in a known state are often called “clean qubits”, but it is usually quite difficult to add new, clean qubits to a system. It is therefore preferable to work with ancillas (ancilla qubits) that are in an unknown state but which are currently not used elsewhere in the quantum computer. Such qubits in an unknown state are referred to herein as “dirty ancillas” to distinguish them from clean ancillas. Typically, there is an abundance of available dirty ancillas at any point during a quantum computation. However, making use of them in a meaningful way was previously not known.